package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	NewList := &ListNode{}
	for head != nil {
		next := head.Next
		head.Next = NewList
		NewList = head
		head = next
	}
	return NewList

}

func reverseList2(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	root := &ListNode{-1, head}
	for head.Next != nil {
		//拿出来
		node := head.Next
		head.Next = node.Next
		//插到头
		node.Next = root.Next
		root.Next = node
	}
	return root.Next
}
